package Sequence;

public class Test0343 {
    public static void main(String[] args) {
        new Solution0343_1().integerBreak(10);
    }
}

class Solution0343_1 {
    public int integerBreak(int n) {
        if (n<4) return n-1;

        int[] dp = new int[n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;

        for (int i = 4; i <= n; i++) {
            int temp = 0;
            for (int j = 1; j <= 3; j++) {
                temp = Math.max(temp, (j*dp[i-j]));
            }
            dp[i]=temp;
        }

        return dp[n];
    }
}
